#include<bits/stdc++.h> 
using namespace std;
long long x[1000000]={0,1,2};
int main()
{
	long long n,k;
	cin>>n;
	for(int i=3;i<1000000;i++)
		x[i]=(2*x[i-1]+x[i-2])%32767;
	while(n--)
	{
		cin>>k;
		cout<<x[k]<<endl;
	}
    return 0;
}
